package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         84,
		Discription: "柱状图中的最大矩形面积",
		Level:       3,
		Labels: map[string]int{
			"栈":   1,
			"单调栈": 1,
			"虚拟栈底": 1,
		},
	})
}

func LargestRectangleArea(heights []int) int {
	//保证第一个元素比任何高度小
	//不要这个虚拟栈底也可以，有了之后就更方便，计算宽度的时候不用考虑有没到数组头了
	stack := []int{-1}
	maxArea := 0

	//任何时候遍历到索引i，[s[top],i)的所有位置的高度必然是比height[s[top]]高的，否则top会出栈
	//同样，（s[top-1],s[top]]的所有位置的高度必然是比height[s[top]]高的。（比top高的都出栈了）
	//所以i处的面积为：height[top]*(top-1,i)区间的长度

	// 遍历所有柱子
	for i := 0; i < len(heights); i++ {
		// 如果当前柱子比栈顶的柱子低，计算面积
		//必须是实时的栈顶
		for len(stack) > 1 && heights[stack[len(stack)-1]] >= heights[i] {
			height := heights[stack[len(stack)-1]]
			stack = stack[:len(stack)-1]
			width := i - stack[len(stack)-1] - 1
			maxArea = max(maxArea, height*width)
		}
		// 将当前柱子的索引压入栈
		stack = append(stack, i)
	}

	// 遍历完所有柱子后，处理栈中剩余的柱子（右边没有比其小的柱子让它出栈）
	for len(stack) > 1 {
		//右边的高度必然都比top大，要不然top会出栈的
		//所以top处的面积为：height(top-1,len(heights)-1]区间的长度
		height := heights[stack[len(stack)-1]]
		stack = stack[:len(stack)-1]
		width := len(heights) - stack[len(stack)-1] - 1
		maxArea = max(maxArea, height*width)
	}

	return maxArea
}
